An elliptical curves cryptosystem (ECC) includes a GF(p) operation based on an integer modular multiplication and a GF(2m) operation based on a polynomial modular multiplication.
A Montgomery modular multiplication algorithm, which is an integer modular multiplication, may be expressed by Equation 1:R=A*B*r−1mod N, (where the radix r=2n)  (1)
where A, B, and N are the multiplicator, multiplicand, and modular number, respectively, and each has n bits (n≧1).
A conventional hardware implementation of a Montgomery modular multiplication algorithm is shown in FIG. 1, which utilizes a multiple modulus selector 1, a booth recoder 12, and an accumulator 2. The multiple modulus selector 1 selects a value for the multiple modulus (0, M, 2M, and 3M) and outputs the selected value to a carry propagation adder (CPA) 14. To obtain a value of 3M, an additional adder may be used, which may increase the hardware size and/or decrease computational speed.
The accumulator 2 may includes two CPAs 14 and 11, each potentially increasing a propagation delay time of an accumulator and/or decreasing computation speed. The CPA 11 receives a partial product value from a multiplicand selector 13 and a previous value P[i] of the output of the accumulator 2. The CPA 11 adds the partial product and P[i]. The output of the CPA 11 is input to the CPA 14 to obtain a resultant accumulation value for an i+1 iteration, P[i+1], obtaining a result for the Montgomery multiplication P[i+1]=ABR−1 mod M.
A polynomial modular multiplication may be expressed may be expressed by Equation 2:P(x)=A(x)B(x)mod G(x)  (2)
where A(x) and B(x) are elements of GF(2m), and G(x) is a primitive polynomial whose degree is m.
A(x), B(x), and G(x) may be expressed may be expressed by Equation 3.A(x)=an−1xn−1+an−2xn−2+ . . . +a1x+a0 B(x)=bn−1xn−1+bn−2xn−2+ . . . +b1x+b0 G(x)=gn−1xn−1+gn−2xn−2+ . . . +g1x+g0  (3)
Generally, a separate multiplier is provided for an integer modular multiplication and a polynomial modular multiplication.